Not applicable.
1. Field of the Invention
The present invention generally relates to a processor that includes a large range of page sizes stored in main memory. More particularly, the invention relates to a computer system with a multi-level page table and translation lookaside buffer (xe2x80x9cTLBxe2x80x9d) that efficiently maps virtual page addresses to physical page addresses for a memory system containing variable sized pages. Still more particularly, the present invention relates to a system that eliminates one level of the page table to efficiently map addresses of large pages in the memory system.
2. Background of the Invention
Almost all computer systems include a processor and a main memory. The main memory functions as the physical working memory of the computer system, where data is stored that has been or will be used by the processor and other system components. In computer systems that implement xe2x80x9cvirtual memory,xe2x80x9d software programs executing on the computer system reference main memory through the use of virtual addresses. A memory management unit (xe2x80x9cMMUxe2x80x9d) translates each virtual address specified by a software program instruction to a physical address that is passed to the main memory in order to retrieve the requested data. The use of virtual memory permits the size of programs to greatly exceed the size of the physical main memory and provides flexibility in the placement of programs in the main memory.
Implementing a virtual memory system requires establishing a correspondence between virtual address space and physical address space in the main memory. The most common technique by which to have virtual address space correspond with physical address space is by using a paging system. A paging system involves separately dividing virtual address space and its corresponding physical address space into contiguous blocks called pages. Each page has a virtual page number (xe2x80x9cVPNxe2x80x9d) address in virtual address space that corresponds to the physical page number (xe2x80x9cPPNxe2x80x9d) address of the page in physical address space.
For each access to main memory, a virtual page number address in virtual address space is translated into the corresponding physical page number address in physical address space and a page offset within the physical page is appended to the physical page number address. Thus, the virtual address subdivided into a Virtual Page Number Address:Page Offset is translated into a physical address consisting of Physical Page Number Address:Page Offset. The physical address is then used to access main memory. Translation of the virtual page number address into its corresponding physical page number address occurs through the use of page tables stored in physical main memory.
In order to reduce the total number of page table main memory accesses required per virtual-to-physical address translation, one or more translation-lookaside buffers are often provided in the MMU. TLB accesses reduce the overall average time required to perform the steps of a virtual-to-physical address translation. A TLB is a cache-like memory, typically implemented in Static Random Access Memory (xe2x80x9cSRAMxe2x80x9d) and/or Content Addressable Memory (xe2x80x9cCAMxe2x80x9d), that holds virtual page number address to physical page number address translations that have recently been fetched from the page table in physical main memory.
Access to a TLB entry holding an output physical page number address corresponding to an input virtual page number address obviates the need for and is typically many orders of magnitude faster than access to the page table in main memory.
If the TLB does not contain the requested translation (i.e., a TLB xe2x80x9cmissxe2x80x9d occurs) then the MMU initiates a search of page tables stored in main memory for the requested virtual page number address. TLB miss handler software executing on the MMU then loads the physical page number address referenced by the virtual page number address into the TLB, where it may be available for subsequent fast access should translation for the same input virtual page number address be required at some future point.
Modem day computer systems implement large virtual address spaces requiring many virtual address bits. A simple page table array with one entry for each possible input virtual page number address, as commonly used in the prior art, is not a feasible solution for implementing the page table because of the slow translation times for such large input addresses and the enormous size of the page table array. To keep page tables required for address translation to a reasonable size and reduce translation times, some virtual to physical address translation schemes implement address translation in multiple stages. In a typical implementation, each stage of the virtual-to-physical address translation requires one or more accesses to the page table that is held in physical main memory. Each stage of the translation requires accessing a different level of the page table using a subfield of bits from the virtual address. Thus, for a virtual memory system that incorporates three stage address translation, the page table may be broken up into three levels with the virtual page number address field from the virtual address being divided into three subfields of bits. One advantage of multistage address translation is the reduction of the amount of main memory needed to store the page tables. The reduction of main memory needed to store the page tables comes from the ability to sparsely populate the page tables and the ability to page out parts of the page table.
The final stage of address translation implemented by the bottom level of the page table (e.g., three level system this would be the third level) prior to generating the physical page number address may be virtually mapped to provide quick access to the page table entries on a TLB miss. Prior to walking each level of the page table to generate the physical page number address, a page table lookup of the virtually mapped bottom level page table entry would occur. The virtually mapped page table lookup to the TLB may also result in a miss, thus resulting in a double translation lookaside buffer miss (virtual page number address TLB miss and virtually mapped final level of the page table TLB miss). Such double TLB misses are slow since a complete walk of the page table structure is then required. Thus, for the three level page table example, a double translation lookaside buffer miss would result in the physical page number address being generated by sequential multiple accesses to each of the three levels of the page table.
One solution to reduce translation lookaside buffer misses is to use larger page sizes so that the same physical main memory can be described by many fewer virtual page number addresses. TLB misses for a system with large page sizes are much less likely. For example, if the small page sizes are such that physical main memory can be mapped into a total of 16 pages while the TLB can only hold eight virtual-to-physical page translations, on the average a random TLB access will miss 50% of the time. Alternatively, if the virtual memory system is implemented with large page sizes such that physical main memory can be mapped into a total of eight pages while the TLB can hold eight virtual-to-physical page translations, an access to the TLB will never miss. However, large page sizes also result in more expensive and complex hardware to access the page offset within the physical page and increase unused fields within the pages (due to internal fragmentation). For this reason, high-performance processors generally allow any of a plurality of page sizes to be selected for different purposes.
High performance processors implementing a virtual memory system that allow multiple page sizes regardless of the page size use the same strategy for all page sizes to translate the virtual page number address into the physical page number address. In such systems, accesses to large size pages using the same translation mapping as small size pages may result in a TLB miss for the virtually mapped final level page table and for every virtual page number address TLB miss (a double TLB miss). This is because the page table is structured for small pages and the page table entries for large page sizes may be duplicated many times. Thus, using the same virtual-to-physical translation scheme for different size pages in a multiple page size virtual memory system may effectively waste half the entries in the TLB (one physical page number address entry corresponds to a virtual page number address and the same physical page number address entry corresponds to a subfield of bits in the virtual page number address) because with large page sizes a double TLB miss is more likely. The second unneeded access to the TLB would further reduce memory system performance and increase average memory access time for data. Finally, modern day virtual memory systems typically include a data cache that contains the data for the most recently translated virtual-to-physical page number addresses. A virtual memory system that supports multiple page sizes but structures the page table for small pages, thus containing duplicate entries for large page sizes, would include in the data cache duplicate copies of the data for each of the large size page entries. A virtual address translation resulting in a double miss to the TLB would also likely result in a miss to the data cache because of the unnecessary duplication of pages.
It would be advantageous if a virtual memory system could perform virtual-to-physical address translation using a multilevel page table that effectively eliminates the problems and disadvantages described above. The address translation scheme must be able to differentiate large page sizes from small page sizes and treat the virtual-to-physical translation of each type of page separately. Separate translation would avoid the duplication of large pages and allow the TLB to map much larger amounts of physical main memory. Despite the apparent performance advantages of such a virtual memory system, to date no such system has been implemented.
The problems noted above are solved in large part by a computer system that includes a processor containing a translation lookaside buffer. The processor is connected to a system memory that contains a page table with multiple levels. The page table translates the virtual address of a page of data stored in system memory into the corresponding physical address of the page of data. If the size of the page is above a certain threshold value, then translation of the page using the multilevel page table occurs by eliminating one or more levels of the page table. In the preferred embodiment, the threshold value is 512 Megabytes. The multilevel page table is only used for translation of the virtual address of the page of data stored in system memory into the corresponding physical address of the page of data if a lookup of the translation lookaside buffer for the virtual address of the page of data results in a miss. The translation lookaside buffer also contains entries from the final level of the page table (i.e., physical addresses of pages of data) that correspond to a subfield of bits from the corresponding virtual addresses of the page of data. Virtual-to-physical address translation using the multilevel page table is not required if the translation lookaside buffer contains the needed physical address of the page of data corresponding to the subfield of bits from the virtual address of the page of data.